home *** CD-ROM | disk | FTP | other *** search
/ Programmer Plus 2007 / Programmer-Plus-2007.iso / Programming / Compilers / Miracle C Compiler / miricleC compiler.msi / Instal01.cab / _58D39A10E5DF48A48AE777E360E07B40 < prev    next >
Encoding:
Text File  |  2000-04-28  |  2.4 KB  |  99 lines
  1. /*    Maze solver
  2.  
  3. Solve maze by finding shortest path in graph. Starting from node A, marked
  4. by 1, each node adjacent to n which has not already been marked with a lower
  5. value is marked with n+1; this process finishes when all paths to B have been
  6. tried and the shortest found. Trace unique path back from B to A.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <system.h>
  12. #include <stdlib.h>
  13.  
  14. int sx=-1, sy,        /* start  A */
  15.     ex=-1, ey=-1,    /* finish B */
  16.     xs=0,  ys=0,    /* size of maze */
  17.     fd=1000;
  18.  
  19. char *maze[100], *work[100];
  20.  
  21. main()
  22. {
  23.    int x=0, y;
  24.    char in[100];
  25.  
  26.    while(*(work[ys]=strcpy(malloc(xs+1),
  27.       maze[ys]=strcpy(malloc(xs?((*in>0)&&(xs!=strlen(in))?
  28.      (exit(0),0):xs)+1:(xs=strlen(in))+1),gets(in)))))
  29.         ys++;
  30.  
  31.    for(x=y=0; y<ys; x=0, y++)
  32.       while(work[y][x])
  33.      switch(work[y][x++])
  34.         {
  35.         case 'A':  if(sx!=-1)
  36.               printf("more than one start"),
  37.               exit(0);
  38.  
  39.                sx=x-1; sy=y; work[sy][sx]=1;  /* start 1 */
  40.                break;
  41.  
  42.         case 'B':  if(ex!=-1)
  43.               printf("more than one end"),
  44.               exit(0);
  45.  
  46.                ex=x-1; ey=y; work[ey][ex]=(char)255;  /* finish -1 */
  47.                break;
  48.  
  49.         case ' ':  work[y][x-1]=(char)254;    /* blanks -2 */
  50.                break;
  51.  
  52.         default :  work[y][x-1]=(char)253;    /* border -3 */
  53.                break;
  54.         }
  55.  
  56.    next(sx,sy,1);    /* find all accessible paths from start A */
  57.  
  58.    if(fd<1000)
  59.       {
  60.       back(ex,ey,fd);  /* trace path of length fd from B back to A */
  61.       for(y=0; y<ys; y++)
  62.      printf("%s\n",maze[y]);
  63.       }
  64.    else
  65.       printf("no solutions");
  66. }
  67.  
  68. next(int x, int y, int t)
  69. {
  70.    int xl, xr, xu, xd;
  71.  
  72.    work[y][x]=t++;
  73.  
  74.    xl=work[y][x-1]; xr=work[y][x+1];
  75.    xu=work[y-1][x]; xd=work[y+1][x];
  76.  
  77.    /* if next to B and no shorter paths, store path length in fd */
  78.  
  79.    if(!(xl+1)|!(xr+1)|!(xu+1)|!(xd+1)) fd=t<fd?t:fd;
  80.  
  81.    /* if next square unreached or by longer path, recurse */
  82.  
  83.    if(xl==-2 || xl>t)  next(x-1,y,t);
  84.    if(xr==-2 || xr>t)  next(x+1,y,t);
  85.    if(xu==-2 || xu>t)  next(x,y-1,t);
  86.    if(xd==-2 || xd>t)  next(x,y+1,t);
  87. }
  88.  
  89. back(int x, int y, int t)
  90. {
  91.    if(!(x==ex && y==ey)) maze[y][x]='+'; work[y][x]=252;
  92.    if(--t==1) return;
  93.  
  94.    if(work[y][x-1]==t) { back(x-1,y,t); return; }
  95.    if(work[y][x+1]==t) { back(x+1,y,t); return; }
  96.    if(work[y-1][x]==t) { back(x,y-1,t); return; }
  97.    if(work[y+1][x]==t) { back(x,y+1,t); return; }
  98. }
  99.